package com.ShangGuiGu.graph;

import lombok.Data;
import lombok.Getter;
import lombok.Setter;
import lombok.Value;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @authoer zsj
 * @date 2022/3/10 16:42
 * <p>
 * 图
 * 图分为无向图和有向图，无向图需要考虑多次访问的问题，而有向图不需要
 * 图的属性有顶点，边，权重
 * 边带权重的图叫做网
 * <p>
 * 深度优先遍历（df）的演示
 * 深度优先遍历，顾名思义，是进行深度的遍历，最大可能的遍历到每一个顶点
 * <p>
 * 从图的root顶点进行开始往下遍历临界点
 * 如果当前顶点的临界点不为空的话，就将当前临界点当作新的root节点，并且为节点做上被访问过的标记
 * 如果当前root顶点的root的临界点为空的话，或者被访问过，我们就回溯，返回上一个root节点
 * 从root节点进行重新开始，访问当前节点未被标记过的节点
 * 一直这样无限循环，直至所有的元素的都被打上了标记
 * 结束遍历
 */
@Data
@Setter
@Getter
public class Graph {

    //所有元素的集合
    private ArrayList<String> vertexList = new ArrayList<String>();
    //是否被访问过
    private boolean[] isVisit;
    //边,模拟邻接矩阵
    private int [][] edges;
    //边的数量
    private int edgesNum;

    //构造方法
    //传进来有几个顶点
    public Graph(int vs){
        this.vertexList = new ArrayList<>(vs);
        this.edges = new int[vs][vs];
        this.isVisit = new boolean[vs];
    }






}
